#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int getNum(int ch)
{
    int result = 0;
    switch (ch)
    {
        case 40:
            result = 1; 
            break;
        case 41:
            result = -1; 
            break;
        case 91:
            result = 2; 
            break;
        case 93:
            result = -2; 
            break;
        case 123:
            result = 3; 
            break;
        case 125:
            result = -3; 
            break;
    }
    return result;
}

bool isValid(char * s){
    int str_len = strlen(s);
    if (str_len % 2 != 0){return false;}
    char stack[str_len];
    memset(stack,0x00,str_len);
    int last=0,now=0,j=0;
    for (int i=0;i<str_len;i++)
    {
        if(last < 0){return false;}
        now = getNum(s[i]);
        if (now == -last)
        {
            j--;
            last = j == 0 ? 0 : getNum(stack[j-1]);
            continue;
        }
        else
        {
            stack[j] = s[i];
            j++;
        }
        last = now;
    }
    if (j == 0){return true;}
    return false;
}